package leetcode_1_200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_93 {
    public static void main(String[] args) {
        System.out.println(restoreIpAddresses("25525511135"));
        System.out.println(restoreIpAddresses("0000"));
        System.out.println(restoreIpAddresses("101023"));
    }
    private static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        String[] fours = new String[4];
        search(s, res, fours, 0, 0);
        return res;
    }
    private static void search(String s, List<String> res, String[] fourS, int indexF, int indexS){
        if (indexF == 4){
            if (indexS == s.length()){
                res.add(fourS[0] + "." + fourS[1] + "." + fourS[2] + "." + fourS[3]);
                return;
            }else
                return;
        }
        if (indexS + 1 <= s.length()){
            String case1 = s.substring(indexS, indexS + 1);
            String[] newFourS = Arrays.copyOf(fourS, fourS.length);
            newFourS[indexF] = case1;
            search(s, res, newFourS, indexF + 1, indexS + 1);
        }
        if (indexS + 2 <= s.length()){
            String case2 = s.substring(indexS, indexS + 2);
            String[] newFourS = Arrays.copyOf(fourS, fourS.length);
            newFourS[indexF] = case2;
            if (case2.charAt(0) != '0')
                search(s, res, newFourS, indexF + 1, indexS + 2);
        }
        if (indexS + 3 <= s.length()){
            String case3 = s.substring(indexS, indexS + 3);
            String[] newFourS = Arrays.copyOf(fourS, fourS.length);
            newFourS[indexF] = case3;
            if (case3.charAt(0) != '0' && Integer.parseInt(case3) <= 255)
                search(s, res, newFourS, indexF + 1, indexS + 3);
        }
    }
}
